package org.example.myleet.p691;

import java.util.*;

public class Solution1 {

    private int answer;

    public int minStickers(String[] stickers, String target) {
        answer = target.length() + 1;
        HashSet<Character> availableCharacters = new HashSet<>(26);
        List<Map<Character, Integer>> stickerCharCounts = new ArrayList<>(stickers.length);
        for (String sticker : stickers) {
            Map<Character, Integer> stickerCharCount = new HashMap<>(26);
            for (char c : sticker.toCharArray()) {
                stickerCharCount.put(c, stickerCharCount.getOrDefault(c, 0) + 1);
                availableCharacters.add(c);
            }
            stickerCharCounts.add(stickerCharCount);
        }
        Map<Character, Integer> targetCharCount = new HashMap<>(26);
        for (char c : target.toCharArray()) {
            if (!availableCharacters.contains(c)) {
                return -1;
            }
            targetCharCount.put(c, targetCharCount.getOrDefault(c, 0) + 1);
        }
        backtrack(targetCharCount, stickerCharCounts, 0, target.length());
        return answer > target.length() ? -1 : answer;
    }

    private void backtrack(Map<Character, Integer> targetCharCount, List<Map<Character, Integer>> stickerCharCounts, int num, int stop) {
        if (targetCharCount.size() == 0) {
            if (answer > num) {
                answer = num;
            }
            return;
        }
        if (num > answer) {
            return;
        }
        if (num > stop) {
            return;
        }
        char char0 = targetCharCount.keySet().stream().findFirst().orElse(null);
        for (Map<Character, Integer> stickerCharCount : stickerCharCounts) {
            if (!stickerCharCount.containsKey(char0)) {
                continue;
            }
            Map<Character, Integer> cacheCharCount = new HashMap<>(26);
            for (Map.Entry<Character, Integer> entry : stickerCharCount.entrySet()) {
                Integer charCount = targetCharCount.get(entry.getKey());
                if (null != charCount) {
                    if (charCount <= entry.getValue()) {
                        cacheCharCount.put(entry.getKey(), charCount);
                        targetCharCount.remove(entry.getKey());
                    } else {
                        cacheCharCount.put(entry.getKey(), entry.getValue());
                        targetCharCount.put(entry.getKey(), charCount - entry.getValue());
                    }
                }
            }
            backtrack(targetCharCount, stickerCharCounts, num + 1, stop);
            //back track
            for (Map.Entry<Character, Integer> entry : cacheCharCount.entrySet()) {
                Integer charCount = targetCharCount.getOrDefault(entry.getKey(), 0);
                targetCharCount.put(entry.getKey(), charCount + entry.getValue());
            }
        }
    }
}
